グラフィックス処理の命令レイテンシ減少のためのシステムおよび方法

专利摘要:
コンパイラ（例えばシェーダ・コンパイラ）の命令スケジューラが、依存する先行命令と後続命令との間の割り出された命令距離に基づいて命令レイテンシを減じる、システム、方法、および装置が開示される。 Ａ
公开号:JP2011514592A
申请号:JP2010547825
申请日:2009-02-20
公开日:2011-05-06
发明作者:チェン、リン
申请人:クゥアルコム・インコーポレイテッドＱｕａｌｃｏｍｍ Ｉｎｃｏｒｐｏｒａｔｅｄ；
IPC主号:G06T15-00

专利说明:

[0001] この開示は、グラフィックス処理において使用されるプログラム・コード中の命令レイテンシを減少すること、特にグラフィックス処理において使用されるシェーダ中の命令レイテンシを減少することに関する。]
背景技術

[0002] グラフィックス処理ユニット（ＧＰＵ）は、ディスプレイ装置上で表示するためのコンピュータ化されたグラフィックスを生成するために使用される専用のグラフィックス・レンダリング装置である。ＧＰＵは、典型的には、汎用中央処理装置（ＣＰＵ）と共に使用されてグラフィック・イメージ・データ（例えば３次元のコンピュータ化されたグラフィック・イメージ・データ）を処理する。そのような場合、ＧＰＵは、多くのプリミティブ・グラフィックス（primitive graphics）演算を実行して、ディスプレイ装置上で表示するための３次元画像を、ＣＰＵを使用してディスプレイ装置上で表示するための画像を描くよりも速く作成することが可能である。典型的には、ＧＰＵは、ハードウェア中のいくつかの複雑なアルゴリズムを実行するハードウェアを含んでいる。]
[0003] 例えば、典型的なＧＰＵは画像ジオメトリ（geometry）を受け取り、パイプライン・アプローチを使用して、例えばディスプレイ装置上での表示に向けて出力されることが可能なグラフィックスを出力する。典型的なグラフィックス・パイプラインは、多くのステージを含んでおり、これらのステージは、パイプライン中で別のステージで恐らく使用されている最中のあるステージからの出力と並列で動作する。例えば、典型的なグラフィックス・パイプラインは、頂点シェーダ、プリミティブ・アセンブリ、ビューポート変換、プリミティブ設定、ラスタ化、隠れた（hidden)プリミティブおよびピクセル除去、属性設定、属性補間（attribute interpolation）、およびフラグメント（断片）・シェーダのステージを具備する。]
[0004] 頂点シェーダは画像のための画像ジオメトリに適用され、画像ジオメトリ中の頂点座標および頂点の属性を生成する。頂点属性は、例えば、１つの頂点と関連する色、法線、およびテクスチャ座標を含んでいる。プリミティブ・アセンブリは、画像ジオメトリに基づいて、頂点から、プリミティブ（primitive、基本要素）（例えば点プリミティブ、線プリミティブ、三角形プリミティブ）を形成する。形成されたプリミティブは、変換（例えば標準化された装置空間からスクリーン空間へプリミティブを変形するビューポート変換）を使用して、ある空間から別の空間へ変形されることが可能である。プリミティブ設定が使用されて、プリミティブの面積（area）およびエッジ係数を割り出し、またオクルジョン・カリング（例えば（背面カリング）および３Ｄクリップ動作を行なうことが可能である。]
[0005] ラスタ化は、プリミティブをプリミティブ中の頂点のＸＹ座標およびプリミティブに含まれているピクセルの数に基づいてピクセルへと変換する。隠れたプリミティブおよびピクセル除去は、プリミティブおよび／またはピクセルのｚ座標を使用して、隠れていると判定されたプリミティブおよびピクセル（例えば画像フレーム中の別のプリミティブまたはピクセルの後ろに位置するプリミティブまたはピクセル、透明なプリミティブまたはピクセル）を特定するとともに除去する。属性設定は、プリミティブ中のピクセルと関連する属性についての属性勾配（attribution gradient）（例えば水平（Ｘ）方向または垂直（Ｙ）方向のいずれかにおいて動いているプリミティブ中の第１ピクセルの属性値と第２ピクセルの属性値との間の差分）を割り出す。属性補間は、割り出された属性勾配値に基づいてプリミティブ中のピクセル上の属性を補間する。補間された属性値は、ピクセル・レンダリングのためにフラグメント・シェーダに送られる。フラグメント・シェーダの結果は、処理された画像をディスプレイ装置上で表示するために、後処理ブロックおよびフレーム・バッファに出力されることが可能である。]
[0006] シェーダ（例えば頂点シェーダ、フラグメント・シェーダ）は、典型的には、グラフィックス・システムまたは他のマルチメディア・システムの中で使用され、プリミティブ（例えば頂点、ピクセル）の属性を算出および制御するコンピュータ・プログラムである。シェーダは、例えば、高水準プログラミング言語または低水準プログラミング言語のようなプログラミング言語で典型的に書かれている。高水準プログラミング言語はＣ＋＋プログラミング言語、などであり得る。アセンブリ言語は低水準言語の例である。]
[0007] シェーダ・コンパイラは、高水準言語または低水準言語で書かれたシェーダ・プログラム・コードを機械レベル言語へ変換する変換器として働く。シェーダが高水準言語で書かれている場合、変換器は、シェーダ・プログラム・コードを、これが書かれている高水準言語から低水準言語に変換し、次いで低水準シェーダ・プログラム・コードを機械レベル命令に変換する。シェーダ・コンパイラの命令スケジューラは、シェーダの実行を早めるために、シェーダの機械語命令を並べ替える。また、シェーダ・コンパイラは、ダミー命令（例えば演算無しまたはＮＯＰ）を挿入することによってハードウェアの時間制約に対処して、シェーダを、これを実行するハードウェアのタイミング制約に一致させる。]
[0008] ハードウェア制約を考慮に入れながらシェーダの命令を最適化することが可能であることは、有益であろう。]
[0009] 本開示は、本技術分野における欠点を対処し、かつ命令のスケジューリングを最適化してグラフィックス処理パイプラインの少なくとも一部（例えば頂点シェーダおよび／またはフラグメント・シェーダのようなシェーダ）を実行するのに使用される１つ以上の方法、装置、およびコンピュータ可読媒体を提供することを目指している。]
[0010] １つ以上の実施形態に従って、複数のグラフィックス処理命令のうちの２つの命令の間の依存が特定される。２つの命令のうちの一方は先行命令を具備し、２つの命令のうちのもう一方は後続命令を具備する。先行命令と後続命令との間の依存と関連する初期エッジ・レイテンシが割り出される。先行命令および後続命令に対応する命令距離が割り出され、これが使用されて初期エッジ・レイテンシを割り出された命令距離の分減じて先行命令と後続命令との間の依存と関連する減じられたエッジ・レイテンシを割り出す。複数のグラフィックス処理命令は、シェーダ（例えば頂点シェーダまたはフラグメント・シェーダ）を実行することが可能である。]
[0011] １つ以上の実施形態に従って、初期エッジ・レイテンシを割り出された命令距離の分減じることによって割り出された減じられたエッジ・レイテンシが使用されて後続命令の実行をスケジューリングする。１つ以上の実施形態に従って、後続命令の実行を開始する前に実行される予定の複数の同期用命令（例えば、独立したシェーダ命令またはＮＯＰ）の数が割り出されて、後続命令の実行を先行命令と同期させる。]
[0012] １つ以上の実施形態に従って、初期エッジ・レイテンシは先行命令と関連するハードウェア・レイテンシであり、また／または先行命令と後続命令との間の依存は、先行命令のデスティネーションが後続命令のソースであるというフロー依存を具備する。]
[0013] １つ以上の実施形態に従って、複数のグラフィックス処理命令のうちの２つの命令の間の依存が特定される。２つの命令のうちの一方は先行命令を具備し、２つの命令のうちのもう一方は後続命令を具備する。先行命令と後続命令との間の依存と関連する初期エッジ・レイテンシが割り出される。先行命令および後続命令に対応する命令距離が割り出され、これが使用されて初期エッジ・レイテンシを割り出された命令距離の分減じて先行命令と後続命令との間の依存と関連する減じられたエッジ・レイテンシを割り出す。命令距離は、先行命令のデスティネーション・オペランドに相当する後続命令の各ソース・オペランドについてのマスク距離を割り出すことと、複数の割り出されたマスク距離のうちの最小のマスク距離を命令距離として選択することと、によって割り出される。]
[0014] １つ以上の実施形態に従って、後続命令のソース・オペランドに関連しかつ命令距離を割り出すのに使用されるマスク距離は、先行命令のデスティネーション・オペランドについての成分マスク、および後続命令のソース・オペランドについての成分マスクを割り出すことと、デスティネーション・オペランドの成分マスクおよびソース・オペランドの成分マスクを連結することによって、成分ストリングを生成することと、成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことと、複数の割り出された成分距離のうちの最小の成分距離をソース・オペランドについてのマスク距離と特定することと、によって割り出される。]
[0015] １つ以上の実施形態に従って、成分の組の中の各成分と関連する成分距離は、成分ストリングを検査して成分ストリングの中の成分の第１の発生の位置を特定することと、成分の第１の発生が特定された場合、成分ストリングを検査して成分ストリングの中の成分の第２の発生の位置を特定することであって、第２の発生は成分ストリングの中の第１の発生の後である、特定することと、成分の第２の発生の位置が特定された場合、成分ストリング中の成分の第１の発生と第２発生との間の成分の数を割り出すことと、成分についての成分距離を割り出された成分の数に設定することと、によって割り出される。]
[0016] １つ以上の実施形態に従って、複数のグラフィックス処理命令は頂点シェーダを実行し、成分の組はＸ、Ｙ、Ｚ、およびＷ成分を具備し、成分距離は成分の組の中のＸ、Ｙ、Ｚ、およびＷ成分の各々に付いて割り出される。１つ以上の実施形態に従って、複数のグラフィックス処理命令はフラグメント・シェーダを実行し、成分の組はＲ、Ｇ、Ｂ、およびＡ成分を具備し、成分距離は成分の組の中のＲ、Ｇ、Ｂ、およびＡ成分の各々に付いて割り出される。]
[0017] この概要は、発明の本質が素早く理解されるように提供された。発明についてのより完全な理解は、その好ましい実施形態の以下の詳細な記述を添付図面とともに参照することによって得られる。]
図面の簡単な説明

[0018] 本開示の上記の特徴および目的は、添付図面とともに使用される以下の記述を参照してより明らかになるだろう。図面において、同様の参照数字は同様の要素を表わす。
本開示の１つ以上の実施形態に従って使用するための典型的な装置を図示するブロック図である。
本開示の１つ以上の実施形態に従ったシェーダ・コンパイラの典型的なブロック図を提供する。
本開示の１つ以上の実施形態に従って使用するための依存性グラフの例を提供する。
本開示の１つ以上の実施形態に従って命令スケジューラ・モジュールによって実行されるエッジ・レイテンシ割り出し工程フローを示す。
本開示の１つ以上の実施形態に従って命令スケジューラ・モジュールによって実行されるエッジ・レイテンシ割り出し工程フローを示す。
本開示の１つ以上の実施形態に従った命令距離割り出し工程フローを示す。
本開示の１つ以上の実施形態に従ったマスク距離割り出し工程フローを示す。
本開示の１つ以上の実施形態に従って先行命令および後続命令の例についての命令距離割り出しの実例を提供する。
本開示の１つ以上の実施形態に関して詳述されたシェーダを実行する命令の例を提供する。
本開示の１つ以上の実施形態に関して詳述されたシェーダを実行する命令の例を提供する。
本開示の１つ以上の実施形態に関して詳述されたシェーダを実行する命令の例を提供する。
本開示の１つ以上の実施形態に関して詳述されたシェーダを実行する命令の例を提供する。
本開示の１つ以上の実施形態に関して詳述されたシェーダを実行する命令の例を提供する。
本開示の１つ以上の実施形態に関して詳述されたシェーダを実行する命令の例を提供する。]
実施例

[0019] 次に、本開示のいくつかの実施形態が、前述の図を参照して詳述される。図において同様の参照数字は同様の構成要素を指す。]
[0020] １つ以上の実施形態に従って、コンパイラ（例えばシェーダ・コンパイラ）の命令スケジューラが依存する先行命令および後続命令との間の割り出された（determine、決定された、特定された）命令距離に基づいて命令レイテンシを減じるシステム、方法、および装置が開示される。本開示の１つ以上の実施形態に従って、シェーダ・コンパイラは、ハードウェア・タイミング制約に対処するともにスケジュール長さ（例えば命令／実行スケジュール中の命令数）を最小化する命令最適化器および命令スケジューラを具備する。シェーダを実行する命令を参照して命令スケジューリングの最適化が本明細書において開示されているが、本開示の実施形態はシェーダを実行する命令の最適化に制限される必要がないことは明らかなはずである。本開示の実施形態が使用されて任意の命令、コンピュータ・プログラム、プログラム・コード、またはプログラムあるいはプログラム・コード・セグメントのスケジューリングを最適化することが可能である。非制限的な例として、本明細書において開示されている実施形態の１つ以上は、複数の成分（例えば２つ、３つ、または４つの成分）から構成されるネイティブな（native）ベクトルをサポートするあらゆるプログラミング言語、およびそのようなプログラミング言語を使用して定義される任意のプログラムまたはプログラム・セグメントとともに使用されることが可能である。]
[0021] 図１は、本開示の１つ以上の実施形態に従って使用するためのグラフィックス処理ユニット（ＧＰＵ）１０４を含んだ典型的な演算装置１００を図示するブロック図である。演算装置１００は、パーソナル・コンピュータ、デスクトップ・コンピュータ、ラップトップ・コンピュータ、ワークステーション、ビデオゲーム・プラットフォームまたは、コンソール、セルラまたは衛星無線電話、地上通信線電話、インターネット電話、携帯型ビデオ・ゲーム装置または携帯情報端末のような携帯型装置、個人用音楽プレーヤ、サーバ、中間ネットワーク装置、メインフレーム・コンピュータ、またはグラフィック状の情報を出力する他の種類の装置を具備する。] 図１
[0022] 図１の例では、演算装置１００は、中央処理装置（ＣＰＵ）１０２、ＧＰＵ１０４およびメモリ・モジュール１１６（例えばランダム・アクセス・メモリ（ＲＡＭ）・メモリ・モジュール）を含んでいる。ＣＰＵ１０２、ＧＰＵ１０４、およびメモリ・モジュール１１６は、バス１０６を使用して通信する。バスは、既知かその後に発見される任意の種類のバスまたは装置相互接続構造（interconnect）を具備することが可能である。ＣＰＵ１０２は汎用または専用マイクロプロセッサを具備することが可能である。例えば、ＣＰＵ１０２は、カリフォルニア州サンタクララのインテル社によって提供されるＣｏｒｅ２プロセッサまたは他の種類のマイクロプロセッサを具備し得る。ＧＰＵ１０４は専用のグラフィックス・レンダリング装置である。ＧＰＵ１０４は、演算装置１００のマザーボードへ統合されるか、演算装置１００のマザーボード中のポート内に設置されるグラフィックス・カード上にあるか、または例えば演算装置１００と協働するように構成されることが可能である。] 図１
[0023] ディスプレイ・ユニット１２４は、演算装置１００に接続され、例えばモニタ、テレビ、プロジェクタ装置、液晶ディスプレイ、プラズマ・ディスプレイ・パネル、発光ダイオード（ＬＥＤ）アレイ、陰極線管ディスプレイ、電子ペーパー、表面伝導型電子放出素子ディスプレイ（ＳＥＤ）、レーザー・テレビ・ディスプレイ、ナノクリスタル・ディスプレイ、または他の種類のディスプレイ・ユニットを具備する。図１の例では、ディスプレイ・ユニット１２４は演算装置１００の一部であり得る。例えば、ディスプレイ・ユニット１２４は移動電話のスクリーンであり得る。あるいは、ディスプレイ・ユニット１２４は、コンピュータ装置１００の外側にあり得、例えば、有線または無線通信接続、または他の接続によって演算装置１００と通信状態にあり得る。非制限的な例として、ディスプレイ・ユニット１２４は、有線または無線接続によってパーソナル・コンピュータに接続されたコンピュータ・モニタまたはフラット・パネル・ディスプレイであり得る。] 図１
[0024] ソフトウェア・アプリケーション１１０はＣＰＵ１０２によって実行されることが可能である。ソフトウェア・アプリケーション１１０は、ＣＰＵ１０２を介して実行可能な任意のソフトウェア・アプリケーション、非制限的な例としてビデオ・ゲーム、グラフィカル・ユーザ・インターフェース・エンジン、工学用コンピュータ支援設計プログラム、または芸術用アプリケーション、あるいは２次元（２Ｄ）グラフィックスまたは３次元（３Ｄ）グラフィックスを使用する他の種類のソフトウェア・アプリケーション、を具備することが可能である。]
[0025] ＣＰＵ１０２がソフトウェア・アプリケーション１１０を実行している際、ソフトウェア・アプリケーション１１０は、グラフィックス処理アプリケーション・プログラミング・インタフェース（ＡＰＩ）１１２（非制限的な例としてＯｐｅｎＶＧ ＡＰＩ、ＯｐｅｎＧＬＡＰＩ、Ｄｉｒｅｃｔ３ＤＡＰＩ、グラフィックス装置インターフェース（ＧＤＩ）、Ｑｕａｒｔｚ、ＱｕｉｃｋＤｒａｗ、または他の種類の２Ｄあるいは３Ｄグラフィックス処理ＡＰＩのうちのいずれか１つ以上）のサブルーチンを呼び出すことが可能である。]
[0026] 少なくとも１つの実施形態に従って、ソフトウェア・アプリケーション１１０がグラフィックス処理ＡＰＩ１１２のサブルーチンを呼び出す際、グラフィックス処理ＡＰＩ１１２はＧＰＵドライバ１１４の１つ以上のサブルーチンを呼び出す。サブルーチンは演算装置１００上のＣＰＵ１０２によって実行される。ＧＰＵドライバ１１４は、例えば、ソフトウェアおよび／またはグラフィックス処理ＡＰＩ１１２とＧＰＵ１０４との間のインターフェースを提供するファームウェア命令の組を具備することが可能である。グラフィックス処理ＡＰＩ１１２がＧＰＵドライバ１１４のサブルーチンを呼び出す際、ＧＰＵドライバ１１４は表示可能なグラフィックス情報をＧＰＵ１０４に生成させるコマンドを作成および発行する。本明細書において開示されている１つ以上の実施形態に従うシェーダ・コンパイラは、ＧＰＵドライバ１１４の構成要素（例えばソフトウェア・モジュール）であることが可能である。ＧＰＵドライバ１１４は、シェーダ・コンパイラを使用してシェーダ・プログラムを機械レベルの命令に変換しＧＰＵ１０４に命令を伝える。例えば、グラフィックス処理ＡＰＩ１１２がグラフィックス・プリミティブのバッチをレンダリングするためのＧＰＵドライバ１１４のサブルーチンを呼び出す際、ＧＰＵドライバ１１４はＧＰＵ１０４に処理設定（processing configuration、処理コンフィギュレーション）を提供する。ＧＰＵ１０４は、これを使用してグラフィックス・プリミティブのバッチをレンダリングする。ＧＰＵ１０４は、グラフィックス・プリミティブのバッチをレンダリングし、例えば、グラフィックス・プリミティブのラスタ・イメージを出力する。]
[0027] ＧＰＵドライバ１１４によって作成されたコマンドは、ＧＰＵ１０４がこのコマンドを実行するのに使用する予定のグラフィックス処理設定（この設定はＧＰＵ１０４によって実行される予定の命令の組を特定することが可能である）、状態レジスタ値の組、およびＧＰＵ１０４がこのコマンドを実行するのに必要であり得る他の種類の情報を特定することが可能である。]
[0028] ＧＰＵドライバ１１４がメモリ１１６中にグラフィックス処理設定を格納している場合、ＧＰＵドライバ１１４は、ＧＰＵドライバ１１４によって作成されたコマンド中のグラフィックス処理設定に対応するメモリ・モジュール１１６中の格納位置を参照することが可能である。ＧＰＵ１０４がコマンドを受け取ると、ＧＰＵ１０４は、ＧＰＵドライバ１１４から受け取った命令の中で参照されているグラフィックス処理設定をメモリ１１６から取得（retrieve）することが可能である。]
[0029] 少なくとも１つの実施形態に従って、ＧＰＵ１０４のコマンド・デコーダ１２６は、ＧＰＵドライバ１１４からのコマンドを解読し、複数の処理要素１２８の１つ以上を設定してコマンドを実行する。非制限的な例として、コマンド・デコーダ１２６はメモリ１１６からグラフィックス処理構成を取得し、このグラフィックス処理設定によって指定されている命令の組を処理要素１２８中にロードする。コマンド・デコーダ１２６は、また、１つ以上の処理要素１２８に入力データを提供するように構成されることが可能である
１つ以上の実施形態に従って、処理要素群１２８はグラフィックス・パイプライン１０８を実行する。そのような実施形態に従って、複数の処理要素１２８は、並行処理においてグラフィックス・パイプライン１０８を実行することが可能である。並行処理では、複数の処理要素１２８は並列にデータを処理することが可能である。このとき、ある処理要素１２８からの出力が別の処理要素１２８への入力として使用される。非制限的な例として、処理要素１２８Ａは、コマンド・デコーダ１２６から受け取った第１の初期入力データの組に対して第１のグラフィックス処理を実行し、処理要素１２８Ｂに第１の中間結果の組を出力する。初期入力データは、例えば、１つ以上の頂点に対応するデータを具備することが可能であり、これらのデータは座標および属性データを具備することが可能である。頂点座標は、例えばＸ、Ｙ、およびＺ（幅、高さ、および深さ）座標と、遠近パラメータ（perspective parameter）を具備するＷ座標と、を有する４次元座標系に基づいてイメージ中の位置を特定する。頂点属性は、例えば、色、法線、および頂点と関連するテクスチャ座標を含むことが可能である。処理要素１２８Ｂは、処理要素１２８Ａによって出力された第１の中間結果の組に対して別のグラフィックス処理を行ない、別の処理要素１２８に第２の中間結果の組を出力することが可能であり、以下、同様である。処理要素１２８Ｂが第２のグラフィックス処理を実行している間、処理要素１２８Ａは、コマンド・デコーダ１２６から受け取った第２の初期入力データの組に対して第１のグラフィックス処理を実行することが可能である。]
[0030] 処理要素群１２８は、このようにして、処理要素１２８Ｎがピクセル・オブジェクトをメモリ・モジュール１１６中の１つ以上のバッファに出力するか、この新しいピクセル・オブジェクトを何らかの他の目的地へ出力するまで、継続することが可能である。ピクセル・オブジェクトはピクセルを記述するデータである。各ピクセル・オブジェクトは複数の色値を指定し得、また、ピクセルの透明度レベルを指定することが可能である。いくつかの状況では、ピクセル・オブジェクトは第１の色フォーマットにおいて第１の色を指定し、第２の色フォーマットにおいて第２の色を指定し得る。]
[0031] 本開示の１つ以上の実施形態に従って、処理要素群１２８の１つは、１つ以上の頂点シェーディング動作（これらの各々は、頂点データ（例えばＸ、Ｙ、Ｚ、およびＷ成分データ）に対して動作する）を実行する頂点シェーダ・ユニットとして構成されることが可能なプログラム可能処理要素を具備する。同様に、処理要素群の１２８のうちのこれと同一のまたは別の１つは、１つ以上のフラグメント・シェーディング動作（これらの各々は、ピクセル・データ（例えばＲ、Ｇ、Ｂ成分データ）に対して動作する）を実行するフラグメント・シェーダとして構成されることが可能なプログラマブル可能処理要素を具備する。]
[0032] 本開示の１つ以上の実施形態に従って、コンパイラは、シェーダ演算（例えば頂点シェーダ、フラグメント・シェーダ演算）を実行するためにプログラム可能処理要素によって実行される予定の命令を含んでいるプログラム・コードを生成する。図２は、プログラム・コード（例えばシェーダ・プログラム・コード）をコンパイルするコンパイラの例を提供する。コンパイラ２００は少なくとも１つの変換器２０２を具備する。変換器２０２は、シェーダ・プログラム・コード（これは高水準プログラミング言語またはアセンブリ言語のいずれかで書かれた命令の組を含んでいる）をプログラム可能処理要素２０６によって認識され得る機械レベル命令に変換する。コンパイラ２００の命令スケジューラ２０４はプログラム可能処理要素２０６によって実行される命令をスケジューリングする。] 図２
[0033] スケジューリングされる予定の機械レベル（すなわち機械実行可能な）命令のグループを具備する入力リストは、命令スケジューラ２０４へ入力される。入力リスト中の、他の命令に依存（すなわち衝突）しない命令は、入力リストから準備完了（ready）リストに移動される。準備完了リストは、実行に向けてスケジューリングされる準備ができている全ての命令を格納する。命令は、スケジューリングされると、準備完了リストからアクティブ・リストに移動される。アクティブ・リストは、現在実行されている命令を格納する。命令は、実行を終えると、アクティブ・リストから結果リストに移動される。結果リストは、スケジューリングされかつ実行を終えた命令を格納する。結果リストは、命令スケジューラの出力を具備する。]
[0034] 命令があるリストから別のリストにいつ移動されるかを制御するゲーティング（gating）条件は、依存グラフ（これは静的レイテンシを特定する）を使用して算出される。非制限的な例として、２つの命令Ｉ１とＩ２との間には、一方の命令Ｉ２が他方の命令Ｉ１の結果に依存する場合、または２つの命令の間に資源の衝突が存在する場合、依存が存在する。２つの命令の間に依存が存在し、命令Ｉ１がＩ２に先行する場合、命令Ｉ１は先行命令（先行命令、predecessor instruction）であるともに命令Ｉ２は後続命令（後続命令、successor instruction）であると判断される。依存グラフが使用されて２つの命令間の依存性を示すことが可能である。]
[0035] 図３は、依存グラフの例またはその部分集合（subset）を提供する。依存グラフは、先行命令と後続命令との間に依存が存在することを示す。依存グラフ中のエッジ３０６が使用されて依存を示すことが可能である。重み３０８がエッジ３０６に関連付けられて、依存を解消するのに必要な命令実行サイクルの数（すなわち回数）を表わすことが可能である。重みはエッジ・レイテンシと称される。エッジ・レイテンシは、入力リストを使用して、静的なレイテンシ、例えば先行命令と関連するハードウェア・レイテンシとして最初に算出される。動的レイテンシは例えば命令／実行サイクル（これらの命令はアクティブ・リスト中にあったものである）で測定されたタイム・スパンである。] 図３
[0036] 先行命令Ｐ１は、ｎ個の後続命令Ｓ１〜Ｓｎを有し得る（ｎは０以上であり得る）。各後続命令Ｓは、先行命令Ｐ１を含めてｎ個の先行命令Ｐ１〜Ｐｎを有し得る。]
[0037] 後続命令の動的レイテンシがその複数の静的レイテンシ（すなわちエッジ・レイテンシ）の１つと同じかそれ以上である場合、後続命令は先行命令の後続体（successor、後続命令）リストから除去されることが可能であり、先行命令は後続体の先行体（predecessor、先行命令）リストから除去されることが可能である。時間が進行する（例えば実行サイクルが起こる）ともに動的レイテンシが増加するに連れて、より多くの後続体および先行命令が除去され得る。アクティブ・リスト上にある指示は、その後続体が全て後続体リストから除去されると、完了する。また、入力リスト上にある指示は、その先行体が全て除去されると実行されるための準備完了となる。したがって、例えば、静的エッジ・レイテンシを最小化して後続命令の実行のタイミングを加速できることは有益である。有利なことに、本開示の１つ以上の実施形態を使用して特定されたエッジ・レイテンシを減少させることは、スケジュールの質を改善し、また、よりコードが小型になるという結果になる。]
[0038] シェーダが書かれているプログラミング言語は特別なグラフィックスやマルチメディアのニーズを満たすために特別な言語構成体を含んでいることがある。特別なシェーダ・プログラミング言語および汎用プログラミング言語（例えばＣ＋＋、および同種のもの）は、同様のデータ種類、配列、構造（structs）、ステートメント、および機能をサポートする。シェーダ・プログラミング言語は汎用言語ほど柔軟でないかもしれなく、またいくつかの一般的な機能に対する幾つかの制限を有しているかもしれないのに対し、シェーダ・プログラミング言語は汎用言語でサポートされていない幾つかの追加機能を有している。例えば、シェーダ言語は、複数の成分（例えば２つ、３つ、または４つの成分）から構成されるネイティブなベクトルに対するサポートを提供することが可能である。汎用プログラミング言語は、通常そのようなベクトルについての元々の（native）サポートを有さない。]
[0039] シェーダ中で使用される典型的なプリミティブは、色および頂点（例えば赤、緑、青（Ｒ、Ｇ、Ｂ）のようなベクトルまたは（Ｘ、Ｙ、Ｚ、Ｗ））を具備する。複数成分ベクトルを使用することは、シェーダ・コンパイラを、汎用言語をコンパイルするコンパイラよりも複雑なものにする。本開示の実施形態は追加の情報を使用してレイテンシを減じるとともに命令スケジューリングを改善する。１つ以上のそのような実施形態に従って、ベクトルおよびそれらの属性を含むシェーダ・プログラミング言語の要素が分析されてエッジ・レイテンシを減じ、その結果、例えば実行待ちの命令の実行タイミングが減じられ、スケジューリングが改善され、コードがより小型化されることが可能である。]
[0040] 命令同士の間に多くの種類の依存が存在する。フロー（すなわち真の）依存が、２つの命令Ｉ１とＩ２との間に存在する。ここで、Ｉ２はＩ１の出力を使用する。真の依存性は、２つの命令によって参照されるレジスタの番号および成分インデックスを検査することによって判断されることが可能である。非制限的な例として、命令Ｉ２は命令Ｉ１の後続体であり、それの複数のソース・オペランドの少なくとも１つとしてレジスタおよび成分（例えば、命令Ｉ１によって出力されるＸ成分）を使用する。]
[0041] 命令Ｉ１とＩ２との間の出力の依存は、両方の命令が同じレジスタへの出力を行なう場合に、存在する。非制限的な例として、命令Ｉ１およびＩ２はレジスタＲ０に出力する。命令Ｉ１とＩ２との間の制御の依存は、実行のフローが論理演算の結果（例えば、if-else条件）によって決定される場合に、存在する。命令Ｉ１とＩ２との間の反依存（anti-dependence）は、命令Ｉ２の出力が、命令Ｉ１の入力と同じレジスタを使用する場合に、存在する。]
[0042] １つ以上の実施形態に従って、初期のエッジ・レイテンシは、先行命令と関連するハードウェア・レイテンシに基づいて割り出されることが可能である。命令Ｉ１とＩ２とが依存し合い、依存が真の依存である場合、ハードウェア・レイテンシの全体が初期エッジ・レイテンシとして使用されることが可能である。この初期エッジ・レイテンシは割り出された命令距離によって減じられることが可能である。１つ以上のそのような実施形態に従って、さらなる分析が実行されて、最初に先行命令のハードウェア・レイテンシであると割り出されたエッジ・レイテンシが割り出された命令距離によって減じられることが可能であるかどうか判断する。本開示の実施形態が使用されてフロー依存および固定のハードウェア・レイテンシが存在する場合以外の場合にエッジ・レイテンシを設定することが可能である。例えば、偽の依存（例えば反依存または出力依存）が存在する場合、エッジ・レイテンシは、１つ以上の実施形態に従って１に設定されることが可能である。]
[0043] ハードウェア・レイテンシは、典型的には、命令を実行するプログラム可能（あるいは他の処理）ユニットのハードウェア設計者によって決定される。ハードウェア・レイテンシは、プログラム可能ユニットによる実行に向けて利用可能な命令群の各々についてのハードウェア・レイテンシを特定するレイテンシ表の一部として提供されることが可能である下記はハードウェア・レイテンシを割り出すための公式による（formal）等式を提供する。]
[0044] HARDWARE_LATENCY(I1、I2)＝スカラ命令Ｉ１およびＩ２についてハードウェア設計者によって提供されるレイテンシ。]
[0045] 下記は、スカラ命令Ｉ１およびＩ２が両方ともＡＤＤである場合、およびＩ１がＡＤＤ命令で、Ｉ２がＢＲＡＮＣＨ命令である場合の上記の等式の例を提供する。]
[0046] HARDWARE_LATENCY (ADD, ADD) = 6
HARDWARE_LATENCY (ADD, BRANCH) = 10
下記は、本明細書において使用されている命令構文の非制限的な例を提供する。この例において、命令Ｉ１とＩ２との間には、ｎが命令Ｉ１およびＩ２の両方について同じ値であり、またＩ１が命令Ｉ２において使用される少なくとも１つの成分を定めているようなフロー依存が存在するものとする。]
[0047] I1: (*i) def Rn.c
I2: (*j) use Rn.d
上記の命令Ｉ１は、成分インデックスｃを有するレジスタＲｎを特定し、また該命令は（ｉ＋１）回繰り返される。命令Ｉ２は、成分インデックスｄを有するレジスタＲｎを使用し、また、命令は（ｊ＋１）回、繰り返される。成分インデックスは例えばＸ、Ｙ、Ｚ、またはＷの１つ以上を指すことが可能である。この非制限的な例の一部として、このオペランド成分インデックスは、これらの命令の一方またはもう一方が繰り返される度にインクリメントされるものとする。上記の命令のベクトルの形態が使用されて２つの命令の間の１または複数の依存を特定することが可能である。下記は、上記のスカラ命令を変換した結果のベクトル形態を提供する。]
[0048] I1: def Rn.mask1
I2: use Rn.mask2
ｍａｓｋ１およびｍａｓｋ２は、命令Ｉ１およびＩ２のそれぞれの成分インデックスによって指されている成分を特定する。命令Ｉ１およびＩ２の両方がレジスタｎ上で動作するので、成分マスク（ｍａｓｋ１とｍａｓｋ２）の検査が、命令Ｉ２が命令Ｉ１に依存するかを判断することが可能である。成分マスクは１または複数の成分を含み得る。成分の例は、ＲＧＢとＸＹＺＷを含んでいる（限定はされない）。成分マスクの例は、ＸＹＺＷ、ＹＺＷＸ、ＸＹ、Ｚを含んでいる（限定はされない）。ｍａｓｋ１およびｍａｓｋ２が、それらが少なくとも１つの成分を共有するという意味で重なり合う場合、依存が存在する。真の依存またはフロー依存が存在する場合、機械レイテンシの全体が初期エッジ・レイテンシとして使用される。Ｉ１からＩ２への依存エッジの初期エッジ・レイテンシは次の通りである。]
[0049] INITIAL LATENCY(I1, I2) =HARDWARE LATENCY(I1, I2)等式１
１つ以上の実施形態に従って、等式１は初期エッジ・レイテンシを特定する。初期エッジ・レイテンシは、下の等式２において例証されているように、２つの依存する命令の間で割り出された距離（命令距離）によって減じられることが可能である。]
[0050] EDGE LATENCY(I1, I2) =HARDWARE LATENCY(I1, I2) - INSTRUCTION DISTANCE等式２
１つ以上の実施形態に従って、命令距離は、成分マスク、成分ストリング、成分距離、および成分マスク距離を使用して割り出されることが可能である。成分マスクは圧縮されたスカラ命令のオペランドから作製されたマスクである。圧縮されたスカラ命令は成分インデックスをインクリメントするかインデックスを維持することによって繰り返されることが可能である。下記は、圧縮されたスカラ命令の例を提供する。]
[0051] (*2) ADDR0.X, (*)R1.Y, R2.X
ここで、＊に続く２は、命令がその最初の実行の後に２回繰り返されること、すなわち命令が合計３回実行されることを示す。第１のオペランドおよび第２のオペランドＲ０およびＲ１と関連する＊は、２つのオペランドに対応する成分インデックスが、命令の１回目および２回目の実行の後にインクリメントされることになっていることを示す。この例では、命令は最初に実行され、さらに２回繰り返される。この圧縮されたスカラ命令は次の３つの圧縮されていないスカラ命令の等価物である。]
[0052] E1: ADDR0.X, R1.Y, R2.X
E2: ADD R0.Y, R1.Z, R2.X
E3: ADD R0.Z, R1.W, R2.X
圧縮されていない命令の１回目の実行（Ｅ１）は、レジスタＲ０、Ｒ１、およびＲ２、ならびにＸ、Ｙ、およびＸ成分をそれぞれ使用する。圧縮されていない命令の実行Ｅ１は、Ｒ１レジスタおよびＲ２レジスタと関連するＸ成分値およびＹ成分値が加えられ、またその結果がレジスタＲ０と関連するＸ成分に格納されるという結果となる。Ｒ０レジスタおよびＲ１レジスタと関連する成分インデックスは、Ｒ０レジスタおよびＲ１レジスタの各々と関連する＊によって示されているように、インクリメントされる。圧縮されていない命令の２回目の実行（Ｅ２）では、Ｒ０レジスタおよびＲ１レジスタと関連する成分はそれぞれＹ成分およびＺ成分である。Ｒ２レジスタと関連する成分（すなわちＸ成分）は不変である。２回目の実行Ｅ２はＲ１レジスタおよびＲ２レジスタと関連するＺ成分値およびＸ成分値を加え、また、その結果はＲ０レジスタと関連するＹ成分に格納される。Ｒ０レジスタおよびＲ１レジスタと関連する成分がそれぞれＺおよびＷとなるようにＲ０レジスタおよびＲ１レジスタと関連する成分インデックスをインクリメントした後、圧縮されていない命令の３回目の実行（Ｅ３）は、レジスタＲ１、Ｒ２と関連するＷ成分値およびＸ成分値を加え、その結果をＲ０レジスタと関連するＺ成分に格納する。]
[0053] レジスタＲ０、Ｒ１、およびＲ２の各々についての成分マスクは、それぞれＸＹＺ、ＹＺＷ、およびＸである。例証を進めると、Ｒ０レジスタのための成分マスクは、圧縮されていないスカラ命令の各々の実行（Ｅ１〜Ｅ３）においてそれぞれ使用されるＲ０レジスタの成分（すなわちそれぞれＸ、Ｙ、Ｚ）を使用して形成される。同様に、Ｒ１レジスタと関連する成分マスクは、命令の実行Ｅ１〜Ｅ３において使用されるＹ成分、Ｚ成分、およびＷ成分から形成され、また、Ｒ２レジスタと関連する成分マスクは、命令の実行Ｅ１〜Ｅ３の全てにおけるこのレジスタのＸ成分を使用することによって形成される。]
[0054] １つ以上の実施形態に従って、ベクトル命令において使用されるスウィズル・マスク（swizzle mask）と異なり、重複する成分をマスクの中に有している複数のスカラ命令から構築されたマスクは、無効な成分マスクである。例えばそのような実施形態に従うと、ＸＸＹは、有効なスウィズル・マスクであるが有効な成分マスクではない。]
[0055] 成分ストリングは、成分マスク（例えば先行命令および後続命令からの２つの成分マスク）を連結することによって生成される。例えば、成分マスクＸＹＺＷと成分マスクＸＹを連結することは、成分ストリングＸＹＺＷＸＹを形成する。成分距離COMPONENT_DIST(C,S)（Ｃは１つの成分（例えばＸ、Ｙ、Ｚ、またはＷのうちの１つ）を表わし、Ｓは成分ストリングを表わす）は、成分ストリングＳにおいて成分Ｃの２回の発生の間に成分Ｃ以外の成分が発生する回数と定義されることが可能である。この距離は、成分ストリングＳ中で成分Ｃが全く発生しないか１回の発生である場合、正の無限大（＋ＩＮＦ）である。]
[0056] 下記は、成分ストリングＸＹＺＷＸＹをＳとして使用し、かつ成分Ｘ、Ｙ、Ｚ、およびＷをＣとして使用した成分距離算出の例を提供する。]
[0057] COMPONENT_DIST (X, XYZWXY) = 3
COMPONENT_DIST (Y, XYZWXY) = 3
COMPONENT_DIST (Z, XYZWXY) = +INF
COMPONENT_DIST (W, XYZWXY) = +INF
成分Ｘを使用した第１の成分距離割り出しでは、成分ストリング中に２回のＸの発生があり、このＸの２回の発生の間に３つの成分ＹＺＷが存在、すなわち発生する。成分Ｙを使用した第２の成分距離割り出しでは、Ｙの発生同士の間に起こる３つの成分ＹＺＷがある。ＺとＷに関する次の２つの成分距離割り出しでは、これらの成分は、いずれも成分ストリング中に１回だけ発生する。したがって、成分距離は＋ＩＮＦに設定される。]
[0058] 成分マスク距離は、成分マスクＭ１およびＭ２を連結することによって形成された成分ストリングを使用して割り出された複数の成分距離のうちの最小の成分距離であると決定されることが可能である。次の等式３は、１つ以上の実施形態に従って成分マスク距離割り出しを公式化したものを提供する。]
[0059] MASK_DIST (M1, M2) = smallest (COMP_DIST (X, M), COMP_DIST (Y, M), COMP_DIST (Z, M), COMP_DIST (W, M))等式３
ここで、ＭはＭ１とＭ２を連結したものである。]
[0060] 例えば、
MASK_DIST (XYZW, XY) = 3である。なぜなら、成分マスクＸＹＺＷとＸＹとを連結したものはＸＹＺＷＸＹであり、Ｘ、Ｙ、Ｚ、およびＷの成分距離はそれぞれ３、３、＋ＩＮＦ、および＋ＩＮＦであるからである。]
[0061] MASK_DIST (YZWX, XY) = 0である。なぜなら、成分マスクＹＺＷＸとＸＹとを連結したものはＹＺＷＸＸＹであり、Ｘ、Ｙ、Ｚ、およびＷの成分距離はそれぞれ０、４、＋ＩＮＦ、および＋ＩＮＦであるからである。]
[0062] オペランド距離は、同じレジスタを使用するソース・オペランドおよびデスティネーション・オペランド（例えば先行命令において使用されるデスティネーション・オペランドおよび後続命令において使用されるソース・オペランド）と関連するマスク群を使用して割り出された成分マスク距離であると定義されることが可能である。オペランド距離は等式３を使用して割り出されたマスク距離である。例えば、Ｍは、先行命令中のオペランドと関連する成分マスクと後続命令中のオペランドと関連する成分マスクとを連結したものである。]
[0063] １つ以上の実施形態に従って、命令距離は複数のオペランド（例えば２つの依存する命令間で共有される各オペランド）の複数のマスク距離のうちの最小のマスク距離（すなわちオペランド距離）であると定義される。先行命令によって特定されるのと同じレジスタを使用する後続命令中に、１または複数のソース・オペランドが存在し得る。同じレジスタを使用する複数のソース・オペランドがある場合、複数のマスク距離が算出され、次いで最小のものが２つの命令の間の距離として選ばれることが可能である。また、１つ以上の実施形態に従って、２つの依存する命令Ｉ１とＩ２（Ｉ１は先行命令であり、Ｉ２は後続命令である）との間の命令距離は、以下のように公式化されることが可能である。]
[0064] INSTR_DIST (I1, I2) = smallest (MASK_DIST (MD, MS1), ... MASK_DIST (MD, MSn))
等式４
ここでＭＤはＩ１のデスティネーション・オペランドの成分マスクであり、ＭＳｉは、Ｉ１のデスティネーション（destination）を使用するＩ２のｉ番目のソース・オペランドであり、ｎはＩ１のデスティネーションを使用するＩ２のソース（source）の総数である。]
[0065] 例えば、次の２つの命令の間の命令距離は１である。]
[0066] I1: ADDR1.XYZ, R2.XYZ, R3.XYZ
I2: MUL R4.X, R1.X, R1.Y
Ｉ１の出力／デスティネーション（Ｒ１．ＸＹＺ）とＩ２の第１および第２入力／ソースとの間の割り出された命令距離は、それぞれ２と１である。したがって、上記のサンプルの命令中のＩ１とＩ２との間の距離は、以下のように表現されることが可能である。]
[0067] INSTR_DIST (I1, I2) = 1
上に詳述されているように、本開示の実施形態は命令距離の分、初期エッジ・レイテンシを減じる。次の等式５が、１つ以上の実施形態に従って使用されるエッジ・レイテンシ決定を公式化したものを提供する。]
[0068] EDGE_LATENCY (I1, I2) = max (1,HARDWARE_LATENCY (I1, I2) - INSTR_DIST (I1, I2))等式５
プログラム可能シェーダ・ユニットは、ＡＬＵ、ＥＬＵ、ＦＬＯＷ、およびＭＥＭを含む（限定はされない）多くの命令形式をサポートする。ＡＬＵ命令は、ＡＤＤ、ＭＵＬ、およびＭＯＶのような（限定はされない）、算術および論理命令を具備する。ＥＬＵ命令は、ＥＸＰ、ＬＯＧ、およびＣＯＳのような（限定はされない）初等関数命令を具備する。ＦＬＯＷ命令は、ＪＵＭＰおよびＢＲＡＮＣＨのような（限定はされない）制御フロー命令を具備する。ＭＥＭ命令は、ＳＡＭＰＬＥおよびＬＯＡＤのような（限定はされない）メモリ指向（memory oriented）命令を具備する。ＡＬＵのような（限定はされない）いくつかの形式は、確定的（deterministic）ハードウェア・レイテンシを有する。ＭＥＭのような（限定はされない）他の命令形式は、非確定的（nondeterministic）ハードウェア・レイテンシを有する。命令セットは、典型的には、例えば非確定的レイテンシについてＷＡＩＴ演算を使用して同期機構をサポートする。]
[0069] 依存関係を有する任意の２つの命令Ｉ１およびＩ２でかつＩ１がＩ２に先行する２つの命令Ｉ１およびＩ２について、本開示の１つ以上の実施形態は以下のようにエッジ・レイテンシを定義する。]
[0070] 反依存または出力依存のような（限定はされない）偽の依存である場合、
EDGE_LATENCY (I1, I2) = 1等式６
依存がフロー依存でありかつＩ１が非確定的レイテンシを有する場合、
EDGE_LATENCY (I1, I2) = 1 等式７
依存がフロー依存でありかつＩ１が固定／確定的レイテンシを有する場合、
EDGE_LATENCY (I1, I2) = max (1,HARDWARE_LATENCY (I1, I2) - INSTR_DIST (I1, I2))
等式８
依存がデータ依存関係ではなく制御依存である場合、
EDGE_LATECNY (I1, I2) = HARDWARE_LATENCY (I1, I2) 等式９
下記は、上記のエッジ・レイテンシの公式化したものの使用を例示する例を提供する。例のため、および例示を目的として、ＡＬＵ型の命令は、５の固定レイテンシおよび２の命令距離を有し、ＥＬＵ型の命令は非確定性レイテンシを有し、ＦＬＯＷ型の命令は１のレイテンシを有するとする。典型的なレイテンシおよび命令距離を使用して、次のエッジ・レイテンシが上記の公式化したものを使用して割り出される。]
[0071] EDGE_LATENCY (ALU, ALU) = 3
EDGE_LATENCY (ALU, ELU) = 3
EDGE_LATENCY (ALU,FLOW) = 3
EDGE_LATENCY (ALU,MEM) = 3
上記の例において、２つの命令の間にはフロー依存があり、したがって、等式８が適用されると仮定されている。各例において、命令Ｉ１は、５の固定レイテンシおよび２の命令距離を有するＡＬＵ型の命令である。２つの命令Ｉ１とＩ２との間にフロー依存が存在すると仮定すると、等式８が使用されてエッジ・レイテンシを割り出す。ＡＬＵ命令の初期エッジ・レイテンシ（これはＡＬＵ型の命令のハードウェア／固定レイテンシ５に相当する）は、２つの命令の間の命令距離２によって減じられ、すなわち、５−２＝３である。]
[0072] 図４（図４は、図４Ａおよび図４Ｂを具備する）は、本開示の１つ以上の実施形態に従って命令スケジューラ・モジュールによって実行されるエッジ・レイテンシ割り出し工程フローを示している。本開示の実施形態は、命令スケジューラ２０４に提供された入力リスト中の命令の対（Ｉ１およびＩ２）の各々について本工程を繰り返す。ここで、対の中の命令のうちの一方は（例えばＩ２）は他方（例えばＩ１）に依存する。] 図４Ａ 図４Ｂ
[0073] ステップ４０２において、２つの命令（Ｉ１とＩ２）の間に依存が存在するか否かの判断がなされる。依存が存在しない場合、工程は、現在の命令対については終了し、次の１対の命令について、検討されるべき命令が無くなるまで、実行されることが可能である。２つの命令の間に依存が存在すると判断された場合、処理は継続してステップ４０４において依存がフロー依存でありかつ先行命令（例えばＩ１）が固定レイテンシを有するか判断する。そうでなければ、処理は継続して図４Ｂのステップ４２０において２つの依存する命令と関連するエッジ・レイテンシを等式６、７、または９によって設定し、この命令対についての処理は終了する。] 図４Ｂ
[0074] ステップ４０４において２つの依存する命令の間にフロー依存が存在しかつ先行命令が固定レイテンシを有すると判断された場合、処理は継続して、ステップ４０６において先行命令および後続命令についての少なくとも１つの成分マスクを特定する。ステップ４０８において、成分ストリングが、ステップ４０６において先行命令および後続命令について特定された成分マスクを使用して特定される。処理は継続して、ステップ４１０において、命令距離をステップ４０８において割り出された成分ストリングを使用して割り出す。]
[0075] 図５は本開示の１つ以上の実施形態に従った命令距離割り出し工程フローを示している。簡略的には、１つ以上の実施形態に従って、１つの命令距離が先行命令および後続命令の複数の共通のオペランド（例えば、レジスタ）を検査して個々の共通のオペランドについてのマスク距離を特定することによって割り出される。先行命令と後続命令との間のフロー依存の場合、後続命令のソース・オペランドは、先行命令のデスティネーション・オペランドを使用する。次に、複数の共通オペランドの各々について特定された複数のマスク距離が検査されて最小のマスク距離を有する共通オペランドを特定する。命令距離は、複数の共通オペランドと関連する複数のマスク距離のうちの最小のものに設定される。] 図５
[0076] 具体的には、ステップ５０２において、先行命令および後続命令によって共用されるオペランドのうちのいずれかが処理に向けて残っているか否かの判断がなされる。そうである場合、処理は継続して、ステップ５０４において、先行命令および後続命令によって共用される次のオペランド（例えば出力を格納するために先行命令によって使用されかつ入力として後続命令によって使用されるレジスタ）を特定する。ステップ５０６において、マスク距離が共通オペランドについて割り出される。]
[0077] 図６は、本開示の１つ以上の実施形態に従った使用のためのマスク距離割り出し工程フローを示している。簡略的には、１つ以上の実施形態に従って、成分マスク（これは先行命令中のデスティネーションであるレジスタと関連する成分を具備する）、および成分マスク（これは後続命令中のソースとして使用される同一のレジスタと関連する成分を具備する）が特定される。特定された複数の成分マスクは成分ストリングを生成するために連結され、複数の成分距離が成分ストリングを使用して割り出される。割り出された複数の成分距離のうちで最小のものがマスク距離として使用される。] 図６
[0078] 図７は、本開示の１つ以上の実施形態に従った、先行命令および後続命令の例についての命令距離割り出しの実例を提供する。先行命令（Ｉ１）および後続命令（Ｉ２）は、図７の７０２において示されている。レジスタＲ１は、命令Ｉ１のデスティネーション・オペランドでありかつ命令Ｉ２のソース・オペランドである。実際には、レジスタＲ１は命令Ｉ２の複数のオペランドのうちの２つのソースである。図６のステップ群がソース成分マスク（ＭＳ１およびＭＳ２）の各々について実行されて、２つのマスク距離が割り出される（レジスタＲ１を使用する命令Ｉ２の中の複数のソース・オペランドの各々について１つ）。表７０４に示すように、命令Ｉ１のデスティネーション・オペランドに対応する成分マスクＭＤはＸＹＺであり、命令Ｉ２の２つのソース・オペランドＭＳ１、ＭＳ２に対応する成分マスクはそれぞれＸ、Ｙである。] 図６ 図７
[0079] 命令Ｉ２の第１のソース・オペランドについては、ステップ６０２において、成分マスクはＭＤおよびＭＳ１（例えばそれぞれ先行命令Ｉ１および後続命令Ｉ２の成分マスク）である。ステップ６０４において、ＭＤおよびＭＳ１が連結されてＸＹＺＸを生成する。ステップ６０６および６０８において成分Ｘ、Ｙ、Ｚ、およびＷが連結ストリングＸＹＺＷと比較されて各成分についての成分距離を割り出す。表７０８は、ステップ６０６および６０８を使用して割り出された各成分についての成分距離を示している。]
[0080] 命令Ｉ２の第２のソース・オペランドについては、ステップ６０２において、成分マスクはＭＤおよびＭＳ２（例えば先行命令Ｉ１および後続命令Ｉ２の成分マスク）である。表７０４に示されているように、ＭＤはＸＹＺであり、また、ＭＳ２はＹである。ステップ６０４において、ＭＤおよびＭＳ２が連結されてＸＹＺＹを生成する。ステップ６０６および６０８において成分Ｘ、Ｙ、Ｚ、およびＷが連結ストリングＸＹＺＹと比較されて各成分についての成分距離を割り出す。表７１２は、ステップ６０６および６０８を使用して割り出された各成分についての成分距離を示している。]
[0081] ステップ６０６において全ての成分が処理されて成分距離を割り出したと判断された場合、処理は継続して、ステップ６１０において割り出された複数の成分距離からマスク距離を割り出す。具体的には、ステップ６１０において、割り出された複数の成分距離のうちの最小の成分距離が特定され、また、ステップ６１０において特定された最小の成分距離がステップ６１２において使用されてマスク距離を設定する。]
[0082] 例では、図７および表７０８を参照すると、ＭＤおよびＭＳ１について決定された最小の成分距離は２である。等式７０６に示されているように、ＭＤおよびＭＳ１のマスク距離は２に設定される。さらなる非制限的な例として、等式７１０に示されているように、ＭＤおよびＭＳ２のマスク距離は１（すなわち表７１４に示されている最小の成分距離）である。] 図７
[0083] 再び図５を参照すると、先行命令と後続命令との間で共用される全てのオペランドが処理されたとステップ５０２で判断された場合、処理は継続してステップ５０８において命令距離を割り出す。具体的には、ステップ５０８において、割り出された複数のマスク距離の最小のマスク距離が特定される。非制限的な例として、および図７の等式７０６および７１０を参照すると、後続命令Ｉ２の第２のソース・オペランドに相当するマスク距離は、後続命令Ｉ２の第１のソース・オペランドに相当するマスク距離より小さい。図５のステップ５１０では、ステップ５０８において特定された最小のマスク距離が使用されて命令距離を設定する。図７に示されている例において、ステップ５１０において命令距離は１にセットされる。] 図５ 図７
[0084] 再び図４を参照すると、ステップ４１２において、先行命令のハードウェア・レイテンシと割り出された命令距離との間の差分が割り出される。ステップ４１４において、割り出された差分が１を超えているか否かの判断がなされる。そうでなければ、処理は継続して、ステップ４２２において、エッジ・レイテンシを１に設定し、また現在の命令対についての処理は終了する。割り出された差分が１を超えているとステップ４１４において判断された場合、処理は継続して、ステップ４１６において、２つの依存する命令の間のエッジ・レイテンシを先行命令のハードウェア・レイテンシと割り出された命令距離との間の差分に設定する。]
[0085] 図４の例示的な工程フローにおいて示されているように、本開示の実施形態は、先行命令と後続命令との間の依存がフロー依存以外である場合、または先行命令が固定ハードウェア・レイテンシを有さない場合、エッジ・レイテンシを１に設定する。下記はいくつかの非制限的な例を提供する。]
[0086] 次の例において、命令Ｉ１はＥＬＵ型命令である。ＥＬＵ型命令はこの例において非確定的レイテンシを有している。命令Ｉ１が非確定的レイテンシを有しているので、等式７が次の各例において使用される。その結果、初期エッジ・レイテンシの値にかかわらずエッジ・レイテンシは１に設定される。]
[0087] EDGE_LATENCY (ELU,ALU) = 1
EDGE_LATENCY (ELU, ELU) = 1
EDGE_LATENCY (ELU,FLOW) = 1
EDGE_LATENCY (ELU,MEM) = 1
次の例では、命令Ｉ１は、命令Ｉ２と依存性を有するとされているＭＥＭのような命令である。この例では、これらの仮定によって、等式６が使用されて、その結果、エッジ・レイテンシは初期エッジ・レイテンシの値にかかわらず１に設定される。]
[0088] EDGE_LATENCY (MEM,ALU) = 1
EDGE_LATENCY (MEM, ELU) = 1
EDGE_LATENCY (MEM,FLOW) = 1
EDGE_LATENCY (MEM, MEM) = 1
次の例では、ＦＬＯＷ型命令である命令Ｉ１は、１のハードウェア・レイテンシを有するとともにデータ依存関係ではなく制御依存を有している。この例では、等式９および命令Ｉ１のハードウェア・レイテンシが使用され、その結果、エッジ・レイテンシは１（初期エッジ・レイテンシ）に設定される。]
[0089] EDGE_LATENCY (FLOW,ALU) = 1
EDGE_LATENCY (FLOW, ELU) = 1
EDGE_LATENCY (FLOW, FLOW) = 1
EDGE_LATENCY (FLOW,MEM) = 1
１つ以上の実施形態に従って、挿入されることが可能な有用な命令（例えば、シェーダの一部を実行する独立した命令）が無い場合、命令スケジューラ２０４は、多くのＮＯＰ、すなわちＷＡＩＴ命令を挿入して命令の実行を同期させる。下記は、上に詳述されている典型的な初期エッジ・レイテンシ、命令距離、および依存性を使用してスケジューリングされるシェーダ・コードの例を提供する。上に詳述されているＡＬＵ命令に関する例において、５の初期エッジ・レイテンシは２の命令距離によって減じられ、その結果、得られたエッジ・レイテンシは、ＡＬＵタイプ命令である第１命令Ｉ１およびＥＬＵ、ＦＬＯＷ、およびＭＥＭ型命令のうちの１つである第２命令Ｉ２とともに等式８を使用して、３であると割り出される。３のエッジ・レイテンシは、第２のＡＬＵ命令が実行される前に３つの実行サイクルがあるはずであることを示している。下の１〜４のケースでは、５のハードウェア・レイテンシについて必要なはずの４つのＮＯＰではなく、２つのＮＯＰが２つの命令Ｉ１とＩ２との間に挿入される。第１の命令が１の実行サイクルを占めるので、２つのＮＯＰ命令は最後の２つの実行サイクルを占め、その結果、３のエッジ・レイテンシが提供され得る。これは、２つのＮＯＰの減少（このことは、実行時間を減じる）につながり、実行される予定の命令がより少なくなる結果となる。]
[0090] ケース１：ＡＬＵ命令はＡＬＵ命令に依存する
ＡＬＵ
ＮＯＰ
ＮＯＰ
ＡＬＵ
ケース２：ＥＬＵ命令はＡＬＵ命令に依存する
ＡＬＵ
ＮＯＰ
ＮＯＰ
ＥＬＵ
ケース３：ＦＬＯＷ命令はＡＬＵ命令に依存する
ＡＬＵ
ＮＯＰ
ＮＯＰ
ＦＬＯＷ
ケース４：ＭＥＭ命令はＡＬＵ命令に依存する
ＡＬＵ
ＮＯＰ
ＮＯＰ
ＭＥＭ
ケース５〜８は先行命令としてＥＬＵ命令を含んでいる。この例において、ＥＬＵ命令は、非確定的レイテンシを有している。このことは、等式７によって、エッジ・レイテンシが１に設定される結果となる。レイテンシが非確定的である（例えば、後続命令が実行されるべき前に実行されるべき実行サイクル（すなわちＮＯＰ）の数が決定可能でない）ので、後続命令はＡＬＵ命令の実行の完了を待つ。]
[0091] ケース５：ＡＬＵ命令はＥＬＵ命令に依存する
ＥＬＵ
（待ち）ＡＬＵ
ケース６：ＥＬＵ命令はＥＬＵ命令に依存する
ＥＬＵ
（待ち）ＥＬＵ
ケース７：ＦＬＯＷ命令はＥＬＵ命令に依存する
ＥＬＵ
（待ち）ＦＬＯＷ
ケース８：ＭＥＭの命令はＥＬＵ命令に依存する
ＥＬＵ
（待ち）ＭＥＭ
ケース９〜１２では、先行命令と後続命令との間の依存は偽の依存であるとされる。このことは、エッジ・レイテンシが等式７によって１に設定される結果となる。先行命令と後続命令との間の依存が偽の依存であるので、後続命令は先行のＭＥＭの命令の実行の完了を待つ。]
[0092] ケース９：ＡＬＵ命令はＭＥＭの命令に依存する
ＭＥＭ
（待ち）ＡＬＵ
ケース１０：ＥＬＵ命令はＭＥＭの命令に依存する
ＭＥＭ
（待ち）ＥＬＵ
ケース１１：ＦＬＯＷ命令はＭＥＭの命令に依存する
ＭＥＭ
（待ち）ＦＬＯＷ
ケース１２：ＭＥＭの命令はＭＥＭの命令に依存する
ＭＥＭ
（待ち）ＭＥＭ
ケース１３〜１６の例では、依存は制御依存とされる。このことは、等式９によって、エッジ・レイテンシが１に設定される結果となる。]
[0093] ケース１３：ＡＬＵ命令はＦＬＯＷ命令に依存する
ＦＬＯＷ
ＡＬＵ
ケース１４：ＥＬＵ命令はＦＬＯＷ命令に依存する
ＦＬＯＷ
ＥＬＵ
ケース１５：ＦＬＯＷ命令はＦＬＯＷ命令に依存する
ＦＬＯＷ
ＦＬＯＷ
ケース１６：ＭＥＭの命令はＦＬＯＷ命令に依存する
ＦＬＯＷ
ＭＥＭ
本開示の実施形態は、初期エッジ・レイテンシを減じるか、不必要なＮＯＰを除去する。例えば、ケース１〜４では、初期エッジ・レイテンシ（これは５に等しい）は２〜３減じられる。４つのＮＯＰを使用する（これは初期エッジ・レイテンシのケースで必要とされるだろう）代わりに、２つのＮＯＰのみが使用され、それによって、２つの不必要なＮＯＰを除去する。典型的なシェーダは、計算が非常に多く（computation intensive）、かなりの数のケース１〜４を含んでいる。したがって、実行リソースを著しく節約することが、本開示の実施形態を使用して達成されることが可能である。]
[0094] 本開示の１つ以上の実施形態に従って、命令スケジューラはエッジ・レイテンシを動的レイテンシと比較して先行体（先行命令）および後続体（後続命令）を除去する。エッジ・レイテンシがより小さいことは、結果的に後続命令と先行命令を早くに除去する結果となる。除去されることが可能な後続命令および先行命令がより多いほど、独立的であってひいてはスケジューリングされる準備ができていると考えられる命令がより多くなり得る。スケジューリングされる準備ができている命令が多いほど、ハードウェア・レイテンシを埋め合わせるためにコードに挿入される必要のあるＮＯＰはより少なくなる。スケジューリングされているコードに挿入される必要のあるＮＯＰの数が減少することは、スケジューリングおよび実行されるコードの効率につながる。コードがシェーダを実行する場合、本開示の実施形態が使用されて、例えば、エッジ・レイテンシの減少を特定し、命令スケジューラのスケジューリング出力を最適化するとともにシェーダの実行を最適化することが可能である。上に詳述されているとともに以下に繰り返されている例は、説明用の例を提供するのに資する。]
[0095] I1: ADDR1.XYZ, R2.XYZ, R3.XYZ
I2: MUL R4.X, R1.X, R1.Y
ＡＤＤとＭＵＬとの間のハードウェア・レイテンシが３である場合、本開示の実施形態を使用しなければ、スケジューリングされたコードは以下のようになるだろう。]
[0096] I1: ADDR1.XYZ, R2.XYZ, R3.XYZ
ＮＯＰ
ＮＯＰ
I2: MUL R4.X, R1.X, R1.Y
上に詳述されているように、少なくとも１つの実施形態を使用して割り出された命令距離は１である。本開示の１つ以上の実施形態を使用すると、エッジ・レイテンシは、ハードウェア・レイテンシから命令距離が減じられたものであると決定されることが可能である。したがって、上記のスケジューリングされたコード例では必要だった２つのＮＯＰの代わりに、１つのＮＯＰのみが次のスケジューリングされたコード例において使用される。以下の命令スケジューラ出力において例示されているように、ＮＯＰの数は、上記のケースにおける２つのＮＯＰではなく、１つのＮＯＰへと減少する。]
[0097] I1: ADDR1.XYZ, R2.XYZ, R3.XYZ
ＮＯＰ
I2: MUL R4.X, R1.X, R1.Y
ＮＯＰの数が減少するのは、命令距離を初期エッジ・レイテンシ（例えばハードウェア・レイテンシ）に適用した結果である。上に詳述されているように、１つ以上の実施形態に従ってこれらの２つの命令について割り出された命令距離は１である。１つ以上のそのような実施形態に従って、先行命令のハードウェア・レイテンシは割り出された命令距離の分減じられて２つの命令の間の減じられたエッジ・レイテンシを生成する。減じられたエッジ・レイテンシの結果、ＮＯＰの数は２から１に減少されることが可能である。このエッジ・レイテンシは２つのサイクルに対応しており、Ｉ１の実行がこの２つの実行サイクルのうちの一方に対応するとともにＮＯＰが２つ目の実行サイクルに対応する。有利なことに、本開示の実施形態は不必要であると判断されたＮＯＰの数を減らして、その結果、命令スケジューラは、２つの依存する命令の間の同期を達成するのに必須なＮＯＰを超えないＮＯＰしか出力しないということが可能である。]
[0098] 図８（図８は、図８Ａ〜図８Ｆを具備する）は、本開示の１つ以上の実施形態に関して詳説されているシェーダを実行する命令の例を提供する。図８Ａおよび図８Ｂは、命令スケジューラへのシェーダ入力を実行する命令の組の例を提供する。図８Ｃおよび図８Ｄは、本開示の１つ以上の実施形態と関連する処理の利点を有さない命令スケジューラによる出力の例を提供する。図８Ｅおよび図８Ｆは、本開示の１つ以上の実施形態と関連する処理から利点を得る命令スケジューラによる出力の例を提供する。] 図８Ａ 図８Ｂ 図８Ｃ 図８Ｄ 図８Ｅ 図８Ｆ
[0099] 図８に示されている例において、本開示の１つ以上の実施形態に従ってエッジ・レイテンシの減少を使用する命令スケジューラは、ＮＯＰの数を、図８Ｃおよび８Ｄにおいて示されている出力中の４８から、図８Ｅおよび８Ｆにおいて示されている出力中の４０まで、効果的に減じる。これは、命令スケジューラのシェーダ命令出力から８つの不必要なＮＯＰの減少である。] 図８Ｃ 図８Ｅ
[0100] ＮＯＰの数の減少の例は、命令３７、４４、５３、および６０に関して観察されることが可能である。各ケースにおいて、ＮＯＰの数は３から１になる。エッジ・レイテンシの減少を使用せずに命令３７を使用することを例証するために、命令スケジューラによるコード・フラグメント出力は、（図８Ｃおよび図８Ｄに示されているように）以下の通りである。] 図８Ｃ 図８Ｄ
[0101] 36(154) type3: (rpt1/syn)fmac r18.z, (r)r16.y, (r)r15.y
37(219) type0: (rpt2)nop
38(157) type3: (lock)fmul dummy, r18.x, r18.x
39(158) type3: (rpt1)fmac r20.x, (r)r18.y, (r)r18.y
コード・フラグメント８１２では、命令３９の両方のソース・オペランドは、命令３６（すなわちｒ１８．ｚ）の結果を使用する。ｆｍａｃのハードウェア・レイテンシが４である場合、本開示の１つ以上の実施形態を使用しないと、４の初期エッジ・レイテンシが使用されて、４のレイテンシ要求が満たされることを保証するために３つのＮＯＰが命令３７に挿入されるべきであると決定する。命令３７は、第１のＮＯＰそして次に２回の反復を実行して３つの実行サイクルを生成する。命令３６の実行と合わせると、命令３８が実行される前に４つの実行サイクルが発生する。]
[0102] 対照的に、本開示の１つ以上の実施形態を用いると、エッジ・レイテンシは減じられて１つのＮＯＰのみが使用される。図８Ｅ中のコード８２２が、以下に転記される。] 図８Ｅ
[0103] 36(154) type3: (rpt1/syn)fmac r18.z, (r)r16.y, (r)r15.y
37(219) type0: nop
38(157) type3: (lock)fmul dummy, r18.x, r18.x
39(158) type3: (rpt1)fmac r20.x, (r)r18.y, (r)r18.y
命令３６および命令３９は、ｆｍａｃすなわち浮動小数点積和である。命令３９は命令３６に依存する。なぜなら、それらの成分マスク（Ｚ）および（ＹＺ）は、少なくとも１つの成分を共有するからである。１つ以上の実施形態を適用すると、（命令Ｉ１としての）命令３６と命令Ｉ１に依存しかつ後続する（命令Ｉ２としての）命令３９との間の命令距離が割り出される。成分距離（Ｃ、Ｓ）は、１の成分の距離を有するＺ以外は、各成分について＋ＩＮＦである。命令距離は複数の成分距離のうちの最小のもの、すなわち１である。ＭＡＳＫ＿ＤＩＳＴ（Ｚ、ＹＺ）が１であるので、命令距離は１と割り出される。ｆｍａｃのデスティネーション・マスクはＺであり、ＺＷではない。なぜなら、ｆｍａｃは成分インデックスをインクリメントしないからである。３８における有用な命令を用いて、１つのＮＯＰのみが必要とされる。]
[0104] １つ以上の例示的な実施形態において、記述されている機能は、ハードウェア、ソフトウェア、および／またはファームウェア、あるいはそれらのあらゆる組合せにおいて実現されることが可能である。ハードウェアにおいて実行される場合、機能は、１つ以上のマイクロプロセッサ、マイクロコントローラ、ディジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイなど（ＦＰＧＡ）において実行されることが可能である。そのような構成要素は通信システム、データ書き込みおよび／または読み出しシステム、または他のシステム内に位置することが可能である。ソフトウェアにおいて実現される場合、関数は１つまたは複数の命令またはコードとして、コンピュータ可読媒体上に格納されるかその上で送信され得る。コンピュータ可読媒体は、有形のコンピュータ記憶装置媒体、およびコンピュータ・プログラムのある位置から別の位置への移動を促進する任意の媒体を含む通信媒体、を含んでいる。記憶媒体は、コンピュータによってアクセスされることが可能な任意の利用可能な物理的媒体であり得る。限定ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、フラッシュ・メモリ、読み出し専用メモリ（ＲＯＭ）、電気的消去可能プログラム可能読み出し専用メモリ（ＥＥＰＲＯＭ）、コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）または他の光学ディスク記憶装置、磁気ディスク記憶装置あるいは他の磁気記憶装置、または命令またはデータ構造の形態の所望のプログラム・コードを格納するために使用されることが可能でかつコンピュータによってアクセスされることが可能な他のあらゆる媒体を具備し得る。用語「コンピュータ可読媒体」は有形のコンピュータ・プログラム製品としても定義されることが可能である。本明細書において使用されているディスク（ｄｉｓｋ）とディスク（ｄｉｓｃ）は、コンパクト・ディスク（ＣＤ）、レーザーディスク（登録商標）、光ディスク、ディジタル多用途ディスク（ＤＶＤ）、フローッピー（登録商標）ディスクおよびブルーレイ・ディスクを含んでいる。ここで、ディスク（ｄｉｓｋ）は通常磁気的にデータを再生し、他方、ディスク（ｄｉｓｃ）はレーザーでデータを光学的に再生する。上記のものの組合せもコンピュータ可読媒体の範囲内に含まれるべきである。]
[0105] 装置および方法が、現在最も実際的でかつ好ましい実施形態であると考えられるものに関して記述されており、本開示が、開示されている実施形態に制限される必要がないことが理解されるべきである。請求項の思想および範囲内に含まれる様々な修正および同様の構成にわたることが意図されている。その範囲はそのような修正および同様の構造を全て包含するように最も広い解釈と一致するべきである。本開示は、次の請求項群の任意のかつ全ての実施形態を含んでいる。]

权利要求:

請求項1
複数のグラフィックス処理命令のうちの２つの命令の間の依存を特定することであって、前記２つの命令のうちの一方は先行命令を具備し、前記２つの命令のうちのもう一方は後続命令を具備する、特定することと、前記先行命令と前記後続命令との間の前記依存と関連する初期エッジ・レイテンシを割り出すことと、前記先行命令および前記後続命令に対応する命令距離を割り出すことと、前記初期エッジ・レイテンシを前記割り出された命令距離によって減じて前記先行命令と前記後続命令との間の前記依存と関連する、減じられたエッジ・レイテンシを割り出すことと、を具備する方法。
請求項2
前記減じられたエッジ・レイテンシを使用して前記後続命令の実行をスケジューリングすること、をさらに具備する、請求項１の方法。
請求項3
前記後続命令の実行を開始する前に実行される予定の複数の同期用命令の数を割り出して前記先行命令および前記後続命令の実行を同期させることであって、前記複数の同期用命令の数は、前記減じられたエッジ・レイテンシを使用して割り出され、各同期用命令は、独立した命令またはＮＯＰである、割り出すこと、をさらに具備する、請求項１の方法。
請求項4
前記複数のグラフィックス処理命令がシェーダを実行する、請求項１の方法。
請求項5
前記シェーダが頂点シェーダである、請求項４の方法。
請求項6
前記シェーダがフラグメント・シェーダである、請求項４の方法。
請求項7
前記初期エッジ・レイテンシが前記先行命令と関連するハードウェア・レイテンシである、請求項１の方法。
請求項8
前記依存が、前記先行命令のデスティネーションが前記後続命令のソースであるというフロー依存を具備する、請求項１の方法。
請求項9
命令距離を割り出すことが、前記先行命令のデスティネーション・オペランドに相当する前記後続命令の各ソース・オペランドについてのマスク距離を割り出すことと、複数の前記割り出されたマスク距離のうちの最小のマスク距離を前記命令距離として選択することと、をさらに具備する、請求項１の方法。
請求項10
前記後続命令の各ソース・オペランドについてのマスク距離を割り出すことが、前記先行命令の前記デスティネーション・オペランドについての成分マスク、および前記後続命令の前記ソース・オペランドについての成分マスクを割り出すことと、前記デスティネーション・オペランドの成分マスクおよび前記ソース・オペランドの成分マスクを連結することによって、成分ストリングを生成することと、前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことと、複数の前記割り出された成分距離のうちの最小の成分距離を前記ソース・オペランドについての前記マスク距離と特定することと、をさらに具備する、請求項９の方法。
請求項11
前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことが、前記成分の組の中の各成分について、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第１の発生の位置を特定することと、前記成分の第１の発生が特定された場合、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第２の発生の位置を特定することであって、前記第２の発生は前記成分ストリングの中の前記第１の発生の後である、特定することと、前記成分の第２の発生の位置が特定された場合、前記成分ストリング中の前記成分の前記第１の発生と前記第２発生との間の成分の数を割り出すことと、前記成分についての前記成分距離を前記割り出された成分の数に設定することと、をさらに具備する、請求項１０の方法。
請求項12
前記複数のグラフィックス処理命令が頂点シェーダを実行し、前記成分の組がＸ、Ｙ、Ｚ、およびＷ成分を具備する、請求項１１の方法。
請求項13
前記複数のグラフィックス処理命令がフラグメント・シェーダを実行し、前記成分の組がＲ、Ｇ、Ｂ、およびＡ成分を具備する、請求項１１の方法。
請求項14
少なくともグラフィックス・パイプラインの一部を実行するように構成された少なくとも１つのプログラム可能処理ユニットと、減じられたエッジ・レイテンシを使用して前記少なくとも１つのプログラム可能演算処理装置による実行のための複数の命令をスケジューリングするように構成された命令スケジューラであって、複数のグラフィックス処理命令のうちの２つの命令の間の依存を特定することであって、前記２つの命令のうちの一方は先行命令を具備し、前記２つの命令のうちのもう一方は後続命令を具備する、特定することと、前記先行命令と前記後続命令との間の前記依存と関連する初期エッジ・レイテンシを割り出すことと、前記先行命令および前記後続命令に対応する命令距離を割り出すことと、前記初期エッジ・レイテンシを前記割り出された命令距離によって減じて前記先行命令と前記後続命令との間の前記依存と関連する、減じられたエッジ・レイテンシを割り出すことと、を実行するように構成されている命令スケジューラと、を具備する装置。
請求項15
前記命令スケジューラが、前記後続命令の実行を開始する前に実行される予定の複数の同期用命令の数を割り出して前記先行命令および前記後続命令の実行を同期させることであって、前記複数の同期用命令の数は、前記減じられたエッジ・レイテンシを使用して割り出され、各同期用命令は、独立した命令またはＮＯＰである、割り出すこと、を実行するようにさらに構成されている、請求項１４の装置。
請求項16
前記少なくとも１つのプログラム可能処理ユニットが、前記複数のグラフィックス処理命令に基づいてシェーダを実行する、請求項１４の装置。
請求項17
前記シェーダが頂点シェーダである、請求項１６の装置。
請求項18
前記シェーダがフラグメント・シェーダである、請求項１６の装置。
請求項19
前記初期エッジ・レイテンシが、前記少なくとも１つのプログラム可能処理ユニットによる前記先行命令の実行と関連するハードウェア・レイテンシである、請求項１４の装置。
請求項20
前記依存が、前記先行命令のデスティネーションが前記後続命令のソースであるというフロー依存を具備する、請求項１４の装置。
請求項21
命令距離を割り出すことを実行するように構成されている前記命令スケジューラが、前記先行命令のデスティネーション・オペランドに相当する前記後続命令の各ソース・オペランドについてのマスク距離を割り出すことと、複数の前記割り出されたマスク距離のうちの最小のマスク距離を前記命令距離として選択することと、をさらに実行するように構成されている、請求項１４の装置。
請求項22
前記後続命令の各ソース・オペランドについてのマスク距離を割り出すことを実行するように構成されている前記命令スケジューラが、前記先行命令の前記デスティネーション・オペランドについての成分マスク、および前記後続命令の前記ソース・オペランドについての成分マスクを割り出すことと、前記デスティネーション・オペランドの成分マスクおよび前記ソース・オペランドの成分マスクを連結することによって、成分ストリングを生成することと、前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことと、複数の前記割り出された成分距離のうちの最小の成分距離を前記ソース・オペランドについての前記マスク距離と特定することと、をさらに実行するように構成されている、請求項２１の装置。
請求項23
前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことを実行するように構成されている前記命令スケジューラが、前記成分の組の中の各成分について、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第１の発生の位置を特定することと、前記成分の第１の発生が特定された場合、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第２の発生の位置を特定することであって、前記第２の発生は前記成分ストリングの中の前記第１の発生の後である、特定することと、前記成分の第２の発生の位置が特定された場合、前記成分ストリング中の前記成分の前記第１の発生と前記第２発生との間の成分の数を割り出すことと、前記成分についての前記成分距離を前記割り出された成分の数に設定することと、をさらに実行するように構成されている、請求項２２の装置。
請求項24
少なくとも１つのプログラム可能処理ユニットが前記複数のグラフィックス処理命令を使用して頂点シェーダを実行し、前記成分の組がＸ、Ｙ、Ｚ、およびＷ成分を具備する、請求項２３の装置。
請求項25
少なくとも１つのプログラム可能処理ユニットが前記複数のグラフィックス処理命令を使用してフラグメント・シェーダを実行し、前記成分の組がＲ、Ｇ、Ｂ、およびＡ成分を具備する、請求項２３の装置。
請求項26
コンピュータによって実行可能なプログラム・コードが格納されるコンピュータ可読メモリ媒体であって、前記プログラム・コードが、複数のグラフィックス処理命令のうちの２つの命令の間の依存を特定することであって、前記２つの命令のうちの一方は先行命令を具備し、前記２つの命令のうちのもう一方は後続命令を具備する、特定することと、前記先行命令と前記後続命令との間の前記依存と関連する初期エッジ・レイテンシを割り出すことと、前記先行命令および前記後続命令に対応する命令距離を割り出すことと、前記初期エッジ・レイテンシを前記割り出された命令距離によって減じて前記先行命令と前記後続命令との間の前記依存と関連する、減じられたエッジ・レイテンシを割り出すことと、を実行するためのコードを具備する、コンピュータ可読メモリ媒体。
請求項27
前記プログラム・コードが、前記減じられたエッジ・レイテンシを使用して前記後続命令の実行をスケジューリングすること、をさらに具備する、請求項２６の媒体。
請求項28
前記後続命令の実行を開始する前に実行される予定の複数の同期用命令の数を割り出して前記先行命令および前記後続命令の実行を同期させることであって、前記複数の同期用命令の数は、前記減じられたエッジ・レイテンシを使用して割り出され、各同期用命令は、独立した命令またはＮＯＰである、割り出すこと、を実行するためのコードをさらに具備する、請求項２６の媒体。
請求項29
前記複数のグラフィックス処理命令がシェーダを実行する、請求項２６の媒体。
請求項30
前記シェーダが頂点シェーダである、請求項２９の媒体。
請求項31
前記シェーダがフラグメント・シェーダである、請求項２９の媒体。
請求項32
前記初期エッジ・レイテンシが前記先行命令と関連するハードウェア・レイテンシである、請求項２６の媒体。
請求項33
前記依存が、前記先行命令のデスティネーションが前記後続命令のソースであるというフロー依存を具備する、請求項２６の媒体。
請求項34
命令距離を割り出すことを実行するように構成されている前記プログラム・コードが、前記先行命令のデスティネーション・オペランドに相当する前記後続命令の各ソース・オペランドについてのマスク距離を割り出すことと、複数の前記割り出されたマスク距離のうちの最小のマスク距離を前記命令距離として選択することと、を実行するためのコードをさらに具備する、請求項２６の媒体。
請求項35
前記後続命令の各ソース・オペランドについてのマスク距離を割り出すことを実行するように構成されている前記プログラム・コードが、前記先行命令の前記デスティネーション・オペランドについての成分マスク、および前記後続命令の前記ソース・オペランドについての成分マスクを割り出すことと、前記デスティネーション・オペランドの成分マスクおよび前記ソース・オペランドの成分マスクを連結することによって、成分ストリングを生成することと、前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことと、複数の前記割り出された成分距離のうちの最小の成分距離を前記ソース・オペランドについての前記マスク距離と特定することと、を実行するためのコードをさらに具備する、請求項３４の媒体。
請求項36
前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すことを実行するように構成されている前記プログラム・コードが、前記成分の組の中の各成分について、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第１の発生の位置を特定することと、前記成分の第１の発生が特定された場合、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第２の発生の位置を特定することであって、前記第２の発生は前記成分ストリングの中の前記第１の発生の後である、特定することと、前記成分の第２の発生の位置が特定された場合、前記成分ストリング中の前記成分の前記第１の発生と前記第２発生との間の成分の数を割り出すことと、前記成分についての前記成分距離を前記割り出された成分の数に設定することと、を実行するためのコードをさらに具備する、請求項３５の媒体。
請求項37
前記複数のグラフィックス処理命令が頂点シェーダを実行し、前記成分の組がＸ、Ｙ、Ｚ、およびＷ成分を具備する、請求項３６の媒体。
請求項38
前記複数のグラフィックス処理命令がフラグメント・シェーダを実行し、前記成分の組がＲ、Ｇ、Ｂ、およびＡ成分を具備する、請求項３６の媒体。
請求項39
少なくともグラフィックス・パイプラインの一部を実行するように構成された少なくとも１つのプログラム可能処理ユニットと、減じられたエッジ・レイテンシを使用して前記少なくとも１つのプログラム可能演算処理装置による実行のための複数の命令をスケジューリングするように構成された命令スケジューリング手段であって、複数のグラフィックス処理命令のうちの２つの命令の間の依存を特定するための手段であって、前記２つの命令のうちの一方は先行命令を具備し、前記２つの命令のうちのもう一方は後続命令を具備する、特定するための手段と、前記先行命令と前記後続命令との間の前記依存と関連する初期エッジ・レイテンシを割り出すための手段と、前記先行命令および前記後続命令に対応する命令距離を割り出すための手段と、前記初期エッジ・レイテンシを前記割り出された命令距離によって減じて前記先行命令と前記後続命令との間の前記依存と関連する、減じられたエッジ・レイテンシを割り出すための手段と、を具備する命令スケジューリング手段と、を具備する装置。
請求項40
前記命令スケジューリング手段が、前記後続命令の実行を開始する前に実行される予定の複数の同期用命令の数を割り出して前記先行命令および前記後続命令の実行を同期させることための手段であって、前記複数の同期用命令の数は、前記減じられたエッジ・レイテンシを使用して割り出され、各同期用命令は、独立した命令またはＮＯＰである、割り出すための手段、をさらに具備する、請求項３９の装置。
請求項41
前記少なくとも１つのプログラム可能処理ユニットが、前記複数のグラフィックス処理命令に基づいてシェーダを実行する、請求項３９の装置。
請求項42
前記シェーダが頂点シェーダである、請求項４１の装置。
請求項43
前記シェーダがフラグメント・シェーダである、請求項４１の装置。
請求項44
前記初期エッジ・レイテンシが、前記少なくとも１つのプログラム可能処理ユニットによる前記先行命令の実行と関連するハードウェア・レイテンシである、請求項３９の装置。
請求項45
前記依存が、前記先行命令のデスティネーションが前記後続命令のソースであるというフロー依存を具備する、請求項３９の装置。
請求項46
命令距離を割り出すための手段が、前記先行命令のデスティネーション・オペランドに相当する前記後続命令の各ソース・オペランドについてのマスク距離を割り出すための手段と、複数の前記割り出されたマスク距離のうちの最小のマスク距離を前記命令距離として選択するための手段と、をさらに具備する、請求項３９の装置。
請求項47
前記後続命令の各ソース・オペランドについてのマスク距離を割り出すための手段が、前記先行命令の前記デスティネーション・オペランドについての成分マスク、および前記後続命令の前記ソース・オペランドについての成分マスクを割り出すための手段と、前記デスティネーション・オペランドの成分マスクおよび前記ソース・オペランドの成分マスクを連結することによって、成分ストリングを生成するための手段と、前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すための手段と、複数の前記割り出された成分距離のうちの最小の成分距離を前記ソース・オペランドについての前記マスク距離と特定するための手段と、をさらに具備する、請求項４６の装置。
請求項48
前記成分ストリングを使用して成分の組の中の各成分と関連する成分距離を割り出すための手段が、前記成分の組の中の各成分について、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第１の発生の位置を特定するための手段と、前記成分の第１の発生が特定された場合、前記成分ストリングを検査して前記成分ストリングの中の前記成分の第２の発生の位置を特定するための手段であって、前記第２の発生は前記成分ストリングの中の前記第１の発生の後である、特定するための手段と、前記成分の第２の発生の位置が特定された場合、前記成分ストリング中の前記成分の前記第１の発生と前記第２発生との間の成分の数を割り出すための手段と、前記成分についての前記成分距離を前記割り出された成分の数に設定するための手段と、をさらに具備する、請求項４７の装置。
請求項49
少なくとも１つのプログラム可能処理ユニットが前記複数のグラフィックス処理命令のうちの命令を使用して頂点シェーダを実行し、前記成分の組がＸ、Ｙ、Ｚ、およびＷ成分を具備する、請求項４８の装置。
請求項50
少なくとも１つのプログラム可能処理ユニットが前記複数のグラフィックス処理命令のうちの命令を使用してフラグメント・シェーダを実行し、前記成分の組がＲ、Ｇ、Ｂ、およびＡ成分を具備する、請求項４８の装置。